package algo.sort;
// 大顶堆
// 数组下标0 不使用。
// 对于节点k:
// 父节点为 k/2
// 子节点为 2k， 2k+1
public class HeapSort<T extends Comparable<? super T>> extends Sort<T>{
    /*
     * 数组的下标0 不能有元素；
     */
    @Override
    public void sort(T[] nums) {
        int N = nums.length - 1;
        for (int k = N/2; k>=1; --k)
            sink(nums, k, N);
        while (N > 1) {
            swap(nums, 1, N--);
            sink(nums, 1, N);
        }
    }

    private void sink(T[] nums, int k, int N) {
        while (k*2 <= N) {
            int j = k*2;

            // 大顶堆
            // 子节点中找最大的, 因为一旦要让子节点上浮， 只能选择更大的那个子节点
            if (j < N && less(nums, j, j+1))
                ++j;

            // 如果 k 的最大的子节点也比 k 小， 跳出
            if (!less(nums, k, j))
                break;
            swap(nums, k, j);
            k = j;
        }
    }


    private void sinkDesc(T[] nums, int k, int N) {
        while (k*2 <= N) {
            int j = k*2;
            // 大顶堆
            // 子节点中找最大的, 因为一旦要让子节点上浮， 只能选择更大的那个子节点
            if (j < N && greater(nums, j, j+1))
                ++j;

            // 如果 k 的最大的子节点也比 k 小， 跳出
            if (!greater(nums, k, j))
                break;

            swap(nums, k, j);
            k = j;
        }
    }

    private boolean less(T[] nums, int i, int j) {
        return nums[i].compareTo(nums[j]) < 0;
    }

    private boolean greater(T[] nums, int i, int j) {
        return nums[i].compareTo(nums[j]) > 0;
    }
    @Override
    public void sortDesc(T[] nums) {
        int N = nums.length - 1;
        for (int k = N/2; k>=1; --k)
            sinkDesc(nums, k, N);
        while (N > 1) {
            swap(nums, 1, N--);
            sinkDesc(nums, 1, N);
        }
    }
}
